package com.lw.leetcode.arr.a;

import java.util.ArrayList;
import java.util.List;

/**
 * 448. 找到所有数组中消失的数字
 *
 * @Author liw
 * @Date 2021/5/23 10:07
 * @Version 1.0
 */
public class FindDisappearedNumbers {

    public List<Integer> findDisappearedNumbers(int[] nums) {
        int length = nums.length;
        List<Integer> list = new ArrayList<>();
        int index = 0;
        while (index < length) {
            int value = nums[index];
            if (value == index + 1) {
                index++;
                continue;
            }


            if (nums[index] == nums[value - 1]) {
                index++;
                continue;
            }
            nums[index] = nums[value - 1];

            nums[value - 1] = value;

        }
        for (int i = 0; i < length; i++) {
            if (nums[i] != i + 1) {
                list.add(i + 1);
            }
        }
        return list;
    }

}
